package com.datastructures2.unionFind;

/**
 * 最好情况一次访问数组，最坏2N+1次访问数组
 * @author MaoLin Wang
 * @date 2020/2/2911:14
 */
public class QuickUnionUF {
    private int[] id;
    private int count;

    public QuickUnionUF(int count) {
        this.count = count;
        id=new int[count];
        for (int i = 0; i < count; i++) {
            id[i]=i;
        }
    }

    public void union(int p,int q){
        int i = find(p);
        int j = find(q);
        if (i!=j){
            id[i]=j;
            count--;
        }
    }
    public int find(int p){
        while (p!=id[p]){
            p=id[p];
        }
        return p;
    }
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }
}
